class Solution
{
public:
    void dfs(string& s, int start, vector<string>& result)
    {
        if (start == s.size())
        {
            result.push_back(s);
            return;
        }

        set<char> charSet;
        for (int i = start; i < s.size(); ++i)
        {
            if (charSet.find(s[i]) != charSet.end())
                continue;
            charSet.insert(s[i]);

            swap(s[start], s[i]);
            dfs(s, start + 1, result);
            swap(s[start], s[i]);
        }
    }

    vector<string> Permutation(string str)
    {
        vector<string> result;
        dfs(str, 0, result);
        return result;
    }
};